package bookForJava.P4;

public class P4_9 {
	static final int N=5;
	static void quickSort(String[] arr,int left,int right)			//快速排序算法
	{
	    String  f,t;
		int rtemp,ltemp;

	    ltemp=left;
	    rtemp=right;
	    f=arr[(left+right)/2];						//分界值
		while(ltemp<rtemp)
		{
	        while(arr[ltemp].compareTo(f)<0)
			{
				++ltemp;
			}
	        while(arr[rtemp].compareTo(f)>0) 
			{
				--rtemp;
			}
	        if(ltemp<=rtemp)
	        {
				t=arr[ltemp];
		        arr[ltemp]=arr[rtemp];
	    	    arr[rtemp]=t;
				--rtemp;
	        	++ltemp;
			}
	    }
	    if(ltemp==rtemp) 
		{
			ltemp++;
		}

	    if(left<rtemp) 
		{
			quickSort(arr,left,ltemp-1);			//递归调用
		}
	    if(ltemp<right) 
		{
			quickSort(arr,rtemp+1,right);			//递归调用
		}
	}

	static void quickSort2(String[] arr,int low,int high)			//快速排序算法
	{
		int start = low;
		int end = high;
		String key = arr[low];

		while(start<end)
		{
			while(start<end && (arr[end].compareTo(key)>=0)) {
				end --;
			}
			if(arr[end].compareTo(key)<0){
				String tmp =  arr[end];
				arr[end] = key;
				arr[start] = tmp;
			}

			while(start<end && (arr[start].compareTo(key)<=0)) {
				start ++;
			}
			if(arr[start].compareTo(key)>0){
				String tmp =  arr[start];
				arr[start] = key;
				arr[end] = tmp;
			}
		}

		if(low<start) quickSort2(arr,low,start-1);
		if(end<high) quickSort2(arr,end+1,high);

	}
	public static void main(String[] args) 
	{
		String[] arr=new String[]{"One","World","Dream","Beijing","Olympic"};	//声明并初始化
		int i;

		System.out.print("排序前：\n");
		for(i=0;i<N;i++)
		{
			System.out.println(arr[i]);					//输出排序前
		}

//		quickSort(arr,0,N-1);							//排序
		quickSort2(arr,0,N-1);							//排序

		System.out.print("排序后：\n");
		for(i=0;i<N;i++)
		{
			System.out.println(arr[i]);					//输出排序后
		}
		

	}
}


